package structures.sort;

import java.util.Arrays;

public class HeapSortDemo {
    private static final int LENGTH = 80000;

    public static void main(String[] args) {
        // 生成数据
        int[] data = new int[LENGTH];
        for (int index = 0; index < data.length; index++) {
            data[index] = (int) (Math.random() * LENGTH);
        }

        // 打印数据
        System.out.println(Arrays.toString(data));

        long startTime = System.currentTimeMillis();
        heapSort(data);
        System.out.println("----------------消耗时间: " + (System.currentTimeMillis() - startTime) + " ms------------");

        // 打印数据
        System.out.println(Arrays.toString(data));
    }

    private static void heapSort(int[] data) {
        // 构建大顶堆模式
        for (int i = data.length / 2 - 1; i >= 0; i--) {
            adjustHeap(data, i, data.length);
        }

        // 首尾值交换
        for (int i = data.length - 1; i > 0; i--) {
            int temp = data[i];
            data[i] = data[0];
            data[0] = temp;
            adjustHeap(data, 0, i);
        }

    }

    private static void adjustHeap(int[] data, int index, int length) {
        if (index >= length) {
            return;
        }
        int temp = data[index];
        for (int i = index * 2 + 1; i < length; i = i *2 + 1) {
            if (i + 1 < length && data[i] < data[i + 1]) {
                i++;
            }
            if (temp < data[i]) {
                data[index] = data[i];
                index = i;
            } else {
                break;
            }
        }
        data[index] = temp;
    }


}

